
public class MinimumWindowSubstring {
	public void tester() {
		System.out.println(minWindow("abc","aabc"));
	}
	
	public String minWindow(String S, String T) {
        // pre-process T string to have only unique char
        
        int tSize = 0;
        String t2 = "";
        for(int i = 0 ; i < T.length() ; i ++) {
        	int index = t2.indexOf(T.charAt(i));
        	if(index == -1) {
        		t2 = t2 + T.charAt(i);
        		tSize ++;
        	}
        }
        
        int [] count = new int [tSize];
        
        for(int i = 0 ; i < T.length() ; i ++) {
        	int index = t2.indexOf(T.charAt(i));
        	count[index]--;
        }
        
        // process string S using double pointer
        
        int min = Integer.MAX_VALUE;
        String result = "";
        int a = 0, b = 0;
        
        while(b < S.length()) {
            int index = t2.indexOf(S.charAt(b));
            b++;
            if(index != -1) {
                count[index]++;
                
                index = t2.indexOf(S.charAt(a));
                while(a<b && (index == -1 || (index >= 0 && count[index] > 0))) {
                    a++;
                    if(index >= 0) {
                        count[index]--;
                    }
                    index = T.indexOf(S.charAt(a));
                }
                
                if(check(count) && min > b-a) {
                    min = b-a;
                    result = S.substring(a, b);
                    
                }
            }
        }
        
        return result;
    }
    
    public boolean check(int [] count) {
    	
        for(int i = 0 ; i < count.length ; i++) {
            if(count[i] < 0) return false;
        }
        return true;
    }
}
